<html>
 <head>
  <meta charset="utf-8"/>
  <meta content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no" name="viewport"/>
  <title>
   谱聚类(Spectal Clustering)——简单易学的机器学习算法  | 数螺 | NAUT IDEA
  </title>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap-theme.min.css" rel="stylesheet"/>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet"/>
  <style type="text/css">
   #xmain img {
                  max-width: 100%;
                  display: block;
                  margin-top: 10px;
                  margin-bottom: 10px;
                }

                #xmain p {
                    line-height:150%;
                    font-size: 16px;
                    margin-top: 20px;
                }

                #xmain h2 {
                    font-size: 24px;
                }

                #xmain h3 {
                    font-size: 20px;
                }

                #xmain h4 {
                    font-size: 18px;
                }


                .header {
	           background-color: #0099ff;
	           color: #ffffff;
	           margin-bottom: 20px;
	        }

	        .header p {
                  margin: 0px;
                  padding: 10px 0;
                  display: inline-block;  
                  vertical-align: middle;
                  font-size: 16px;
               }

               .header a {
                 color: white;
               }

              .header img {
                 height: 25px;
              }
  </style>
  <script src="http://cdn.bootcss.com/jquery/3.0.0/jquery.min.js">
  </script>
  <script src="http://nautstatic-10007657.file.myqcloud.com/static/css/readability.min.js" type="text/javascript">
  </script>
  <script type="text/javascript">
   $(document).ready(function() {
                 var loc = document.location;
                 var uri = {
                  spec: "http://dataunion.org/19721.html",
                  host: "http://dataunion.org",
                  prePath: "http://dataunion.org",
                  scheme: "http",
                  pathBase: "http://dataunion.org/"
                 };
    
                 var documentClone = document.cloneNode(true);
                 var article = new Readability(uri, documentClone).parse();
     
                 document.getElementById("xmain").innerHTML = article.content;
                });
  </script>
  <!-- 1466461247: Accept with keywords: (title(0.4):数盟,算法,社区,易学,聚类, topn(0.4):社区,定义,数盟,深度学习,行业资讯,类别,子网,数据挖掘,拉普拉斯,职业规划,边的,基础架构,文章,方法,节点,结构,特征值,函数,特征向量,矩阵,邻接矩阵,目标,算法,顶点,优化,编程语言,利用,稀疏,网络,聚类).-->
 </head>
 <body onload="">
  <div class="header">
   <div class="container">
    <div class="row">
     <div class="col-xs-6 col-sm-6 text-left">
      <a href="/databee">
       <img src="http://nautidea-10007657.cos.myqcloud.com/logo_white.png"/>
      </a>
      <a href="/databee">
       <p>
        数螺
       </p>
      </a>
     </div>
     <div class="hidden-xs col-sm-6 text-right">
      <p>
       致力于数据科学的推广和知识传播
      </p>
     </div>
    </div>
   </div>
  </div>
  <div class="container text-center">
   <h1>
    谱聚类(Spectal Clustering)——简单易学的机器学习算法
   </h1>
  </div>
  <div class="container" id="xmain">
   ﻿﻿
   <title>
    谱聚类(Spectal Clustering)——简单易学的机器学习算法 | 数盟社区
   </title>
   <!-- All in One SEO Pack 2.2.7.6.2 by Michael Torbert of Semper Fi Web Design[32,83] -->
   <!-- /all in one seo pack -->
   <!--
<div align="center">
<a href="http://strata.oreilly.com.cn/hadoop-big-data-cn?cmp=mp-data-confreg-home-stcn16_dataunion_pc" target="_blank"><img src="http://dataunion.org/wp-content/uploads/2016/05/stratabj.jpg"/ ></a>
</div>
-->
   <header id="header-web">
    <div class="header-main">
     <hgroup class="logo">
      <h1>
       <a href="http://dataunion.org/" rel="home" title="数盟社区">
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/logo.png"/>
       </a>
      </h1>
     </hgroup>
     <!--logo-->
     <nav class="header-nav">
      <ul class="menu" id="menu-%e4%b8%bb%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-71" id="menu-item-71">
        <a href="http://dataunion.org/category/events" title="events">
         活动
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22457" id="menu-item-22457">
          <a href="http://dataunion.org/2016timeline">
           2016档期
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22459" id="menu-item-22459">
          <a href="http://dataunion.org/category/parterc">
           合作会议
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor current-menu-parent current-post-parent menu-item-has-children menu-item-20869" id="menu-item-20869">
        <a href="http://dataunion.org/category/tech" title="articles">
         文章
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20867" id="menu-item-20867">
          <a href="http://dataunion.org/category/tech/base" title="base">
           基础架构
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3302" id="menu-item-3302">
          <a href="http://dataunion.org/category/tech/ai" title="ai">
           人工智能
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3303" id="menu-item-3303">
          <a href="http://dataunion.org/category/tech/analysis" title="analysis">
           数据分析
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21920" id="menu-item-21920">
          <a href="http://dataunion.org/category/tech/dm">
           数据挖掘
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3314" id="menu-item-3314">
          <a href="http://dataunion.org/category/tech/viz" title="viz">
           可视化
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3305" id="menu-item-3305">
          <a href="http://dataunion.org/category/tech/devl" title="devl">
           编程语言
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-20876" id="menu-item-20876">
        <a href="http://dataunion.org/category/industry">
         行业
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-16328" id="menu-item-16328">
          <a href="http://dataunion.org/category/industry/case" title="case">
           行业应用
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-2112" id="menu-item-2112">
          <a href="http://dataunion.org/category/industry/demo" title="demo">
           Demo展示
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21562" id="menu-item-21562">
          <a href="http://dataunion.org/category/industry/news">
           行业资讯
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-311" id="menu-item-311">
        <a href="http://dataunion.org/category/sources" title="sources">
         资源
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20870" id="menu-item-20870">
        <a href="http://dataunion.org/category/books" title="book">
         图书
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21363" id="menu-item-21363">
        <a href="http://dataunion.org/category/training">
         课程
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-21853" id="menu-item-21853">
        <a href="http://dataunion.org/category/jobs">
         职位
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22050" id="menu-item-22050">
          <a href="http://dataunion.org/category/career">
           职业规划
          </a>
         </li>
        </ul>
       </li>
      </ul>
     </nav>
     <!--header-nav-->
    </div>
   </header>
   <!--header-web-->
   <div id="main">
    <div id="soutab">
     <form action="http://dataunion.org/" class="search" method="get">
     </form>
    </div>
    <div id="container">
     <nav id="mbx">
      当前位置：
      <a href="http://dataunion.org">
       首页
      </a>
      &gt;
      <a href="http://dataunion.org/category/tech">
       文章
      </a>
      &gt;  正文
     </nav>
     <!--mbx-->
     <article class="content">
      <header align="centre" class="contenttitle">
       <div class="mscc">
        <h1 class="mscctitle">
         <a href="http://dataunion.org/19721.html">
          谱聚类(Spectal Clustering)——简单易学的机器学习算法
         </a>
        </h1>
        <address class="msccaddress ">
         <em>
          4,350 次阅读 -
         </em>
         <a href="http://dataunion.org/category/tech" rel="category tag">
          文章
         </a>
        </address>
       </div>
      </header>
      <div class="content-text">
       <blockquote>
        <p>
         作者:
         <a class="user_name" href="http://my.csdn.net/google19890102" target="_blank">
          zhiyong_will
         </a>
         出处：
         <a href="http://blog.csdn.net/google19890102">
          zhiyong_will的博客
         </a>
        </p>
       </blockquote>
       <h1>
        一、复杂网络中的一些基本概念
       </h1>
       <h2>
        <p name="t1">
        </p>
        1、复杂网络的表示
       </h2>
       <div>
        在复杂网络的表示中，复杂网络可以建模成一个图
        <em>
         G=(V,E)
        </em>
        ，其中，
        <em>
         V
        </em>
        表示网络中的节点的集合，
        <img src="http://latex.codecogs.com/gif.latex?E"/>
        表示的是连接的集合。在复杂网络中，复杂网络可以是无向图、有向图、加权图或者超图。
       </div>
       <h2>
        <p name="t2">
        </p>
        2、网络簇结构
       </h2>
       <div>
        网络簇结构(network cluster structure)也称为网络社团结构(network community structure)，是复杂网络中最普遍和最重要的拓扑属性之一。网络簇是整个网络中的稠密连接分支，具有同簇内部节点之间相互连接密集，不同簇的节点之间相互连接稀疏的特征。
       </div>
       <h2>
        <p name="t3">
        </p>
        3、复杂网络的分类
       </h2>
       <div>
        复杂网络主要分为：随机网络，小世界网络和无标度网络。
       </div>
       <h1>
        <p name="t4">
        </p>
        二、谱方法介绍
       </h1>
       <h2>
        <p name="t5">
        </p>
        1、谱方法的思想
       </h2>
       <div>
        在复杂网络的网络簇结构存在着同簇节点之间连接密集，不同簇节点之间连接稀疏的特征，是否可以根据这样的特征对网络中的节点进行聚类，使得同类节点之间的连接密集，不同类别节点之间的连接稀疏？
       </div>
       <div>
        在谱聚类中定义了“截”函数的概念，当一个网络被划分成为两个子网络时，“截”即指子网间的连接密度。谱聚类的目的就是要找到一种合理的分割，使得分割后形成若干子图，连接不同的子图的边的权重尽可能低，即“截”最小，同子图内的边的权重尽可能高。
       </div>
       <h2>
        <p name="t6">
        </p>
        2、“截”函数的具体表现形式
       </h2>
       <div>
        “截”表示的是子网间的密度，即边比较少。以二分为例，将图聚类成两个类：
        <em>
         S
        </em>
        类和
        <em>
         T
        </em>
        类。假设用
        <em>
         cut(S,T)
        </em>
        来表示图的划分，我们需要的结果为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?min\;&amp;space;cut\left&amp;space;(&amp;space;S,T&amp;space;\right&amp;space;)=\sum_{i\in&amp;space;S;j\in&amp;space;T}e_{ij}=W\left&amp;space;(&amp;space;S,T&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        其中
        <em>
         W(S,T)
        </em>
        表示的是类别
        <em>
         S
        </em>
        和
        <em>
         T
        </em>
        之间的权重。对于
        <em>
         k
        </em>
        个不同的类别A1,A2,…,Ak，优化的目标为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?min\;&amp;space;cut\left&amp;space;(&amp;space;A_1,A_2,\cdots&amp;space;,A_k&amp;space;\right&amp;space;)=\frac{1}{2}\sum_{i=1}^{k}W\left&amp;space;(&amp;space;A_i,\bar{A}_i&amp;space;\right&amp;space;)"/>
       </div>
       <h2>
        <p name="t7">
        </p>
        3、基本“截”函数的弊端
       </h2>
       <div>
        对于上述的“截”函数，最终会导致不好的分割，如二分类问题:
       </div>
       <div>
        <img src="http://img.blog.csdn.net/20150514154340387?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZ2xlMTk4OTAxMDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast"/>
       </div>
       <div>
        上述的“截”函数通常会将图分割成一个点和其余n-1个点。
       </div>
       <h2>
        <p name="t8">
        </p>
        4、其他的“截”函数的表现形式
       </h2>
       <div>
        为了能够让每个类都有合理的大小，目标函数中应该使得
        <img src="http://latex.codecogs.com/gif.latex?A_1,A_2,\cdots&amp;space;,A_k"/>
        足够大，则提出了
        <img src="http://latex.codecogs.com/gif.latex?RatioCut\left&amp;space;(&amp;space;A_1,A_2,\cdots&amp;space;,A_k&amp;space;\right&amp;space;)"/>
        或者
        <img src="http://latex.codecogs.com/gif.latex?NCut\left&amp;space;(&amp;space;A_1,A_2,\cdots&amp;space;,A_k&amp;space;\right&amp;space;)"/>
        ：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?RatioCut\left&amp;space;(&amp;space;A_1,A_2,\cdots&amp;space;,A_k&amp;space;\right&amp;space;)=\frac{1}{2}\sum_{i=1}^{k}\frac{W\left&amp;space;(&amp;space;A_i,\bar{A}_i&amp;space;\right&amp;space;)}{\left&amp;space;|&amp;space;A_i&amp;space;\right&amp;space;|}"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?NCut\left&amp;space;(&amp;space;A_1,A_2,\cdots&amp;space;,A_k&amp;space;\right&amp;space;)=\frac{1}{2}\sum_{i=1}^{k}\frac{W\left&amp;space;(&amp;space;A_i,\bar{A}_i&amp;space;\right&amp;space;)}{vol\left&amp;space;(&amp;space;A_i&amp;space;\right&amp;space;)}"/>
       </div>
       <div>
        其中
        <img src="http://latex.codecogs.com/gif.latex?\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|"/>
        表示
        <em>
         A
        </em>
        类中包含的顶点的数目
       </div>
       <h1>
        <p name="t9">
        </p>
        三、Laplacian矩阵
       </h1>
       <h2>
        <p name="t10">
        </p>
        1、Laplacian矩阵的定义
       </h2>
       <div>
        拉普拉斯矩阵(Laplacian Matrix)，也称为基尔霍夫矩阵，是图的一种矩阵表示形式。
       </div>
       <div>
        对于一个有
        <em>
         n
        </em>
        个顶点的图
        <em>
         G=(V,E)
        </em>
        ，其Laplacian矩阵定义为：
       </div>
       <div>
        <em>
         L=D—A
        </em>
       </div>
       <div>
        其中，
        <em>
         D
        </em>
        为图的度矩阵，
        <em>
         A
        </em>
        为图的邻接矩阵。
       </div>
       <h2>
        <p name="t11">
        </p>
        2、度矩阵的定义
       </h2>
       <div>
        度矩阵是一个对角矩阵，主角线上的值由对应的顶点的度组成。
       </div>
       <div>
        对于一个有
        <em>
         n
        </em>
        个顶点的图
        <em>
         G=(V,E)
        </em>
        ，其邻接矩阵为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?A=\begin{pmatrix}&amp;space;w_{11}&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;w_{1n}\\&amp;space;\vdots&amp;space;&amp;&amp;space;&amp;&amp;space;\vdots&amp;space;\\&amp;space;w_{n1}&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;w_{nn}&amp;space;\end{pmatrix}"/>
       </div>
       <div>
        其度矩阵为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?D=\begin{pmatrix}&amp;space;d_1&amp;space;&amp;&amp;space;0&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;0\\&amp;space;0&amp;space;&amp;&amp;space;d_2&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;0\\&amp;space;\vdots&amp;space;&amp;&amp;space;\vdots&amp;space;&amp;&amp;space;&amp;&amp;space;\vdots&amp;space;\\&amp;space;0&amp;space;&amp;&amp;space;0&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;d_n&amp;space;\end{pmatrix}"/>
       </div>
       <div>
        其中
        <img src="http://latex.codecogs.com/gif.latex?d_i&amp;space;=\sum_{j=1}^{n}d_{ij}"/>
        。
       </div>
       <h2>
        <p name="t12">
        </p>
        3、Laplacian矩阵的性质
       </h2>
       <div>
        <ol>
         <li>
          Laplacian矩阵
          <em>
           L
          </em>
          是对称半正定矩阵；
         </li>
         <li>
          Laplacian矩阵
          <em>
           L
          </em>
          的最小特征值是0，相应的特征向量是
          <em>
           I
          </em>
          ；
         </li>
         <li>
          Laplacian矩阵
          <em>
           L
          </em>
          有
          <em>
           n
          </em>
          个非负实特征值：
          <img src="http://latex.codecogs.com/gif.latex?0=\lambda&amp;space;_1\leq&amp;space;\lambda&amp;space;_2\leq&amp;space;\cdots&amp;space;\leq&amp;space;\lambda&amp;space;_n"/>
          ，且对于任何一个实向量
          <em>
           f
          </em>
          ，都有下面的式子成立：
         </li>
        </ol>
        <div>
         <img src="http://latex.codecogs.com/gif.latex?{f}'Lf=\frac{1}{2}\sum_{i,j=1}^{n}w_{ij}\left&amp;space;(&amp;space;f_i-f_j&amp;space;\right&amp;space;)^2"/>
        </div>
       </div>
       <div>
        性质3的证明：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&amp;space;{f}'Lf&amp;space;&amp;={f}'Df-{f}'Af&amp;space;\\&amp;space;&amp;=&amp;space;\sum_{i=1}^{n}d_if_i^2-\sum_{i,j=1}^{n}f_if_jw_{ij}\\&amp;space;&amp;=&amp;space;\frac{1}{2}\left&amp;space;(&amp;space;\sum_{i=1}^{n}d_if_i^2-2\sum_{i,j=1}^{n}f_if_jw_{ij}+\sum_{j=1}^{n}d_jf_j^2&amp;space;\right&amp;space;)\\&amp;space;&amp;=&amp;space;\frac{1}{2}\sum_{i,j=1}^{n}w_{ij}\left&amp;space;(&amp;space;f_i-f_j&amp;space;\right&amp;space;)^2&amp;space;\end{align*}"/>
       </div>
       <h2>
        <p name="t13">
        </p>
        4、不同的Laplacian矩阵
       </h2>
       <div>
        除了上述的拉普拉斯矩阵，还有规范化的Laplacian矩阵形式：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?L=D^{-\frac{1}{2}}\left&amp;space;(&amp;space;D-A&amp;space;\right&amp;space;)D^{-\frac{1}{2}}"/>
       </div>
       <h1>
        <p name="t14">
        </p>
        四、Laplacian矩阵与谱聚类中的优化函数的关系
       </h1>
       <h2>
        <p name="t15">
        </p>
        1、由Laplacian矩阵到“截”函数
       </h2>
       <div>
        对于二个类别的聚类问题，优化的目标函数为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?min\;&amp;space;RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        定义向量
        <img src="http://latex.codecogs.com/gif.latex?f={\left&amp;space;(&amp;space;f_1,f_2,\cdots&amp;space;,f_n&amp;space;\right&amp;space;)}'"/>
        ，且
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?f_i=\begin{cases}&amp;space;\sqrt{\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}}&amp;space;&amp;&amp;space;\text{&amp;space;if&amp;space;}&amp;space;v_i\in&amp;space;A&amp;space;\\&amp;space;-\sqrt{\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}}&amp;space;&amp;&amp;space;\text{&amp;space;if&amp;space;}&amp;space;v_i\in&amp;space;\bar{A}&amp;space;\end{cases}"/>
       </div>
       <div>
        而已知：
        <img src="http://latex.codecogs.com/gif.latex?{f}'Lf=\frac{1}{2}\sum_{i,j=1}^{n}w_{ij}\left&amp;space;(&amp;space;f_i-f_j&amp;space;\right&amp;space;)^2"/>
        ，则
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;\frac{1}{2}\sum_{i\in&amp;space;A,j\in&amp;space;\bar{A}}w_{ij}\left&amp;space;(&amp;space;\sqrt{\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}}+\sqrt{\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}}&amp;space;\right&amp;space;)^2+\frac{1}{2}\sum_{i\in&amp;space;\bar{A},j\in&amp;space;A}w_{ij}\left&amp;space;(&amp;space;-\sqrt{\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}}-\sqrt{\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}}&amp;space;\right&amp;space;)^2"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;\frac{1}{2}\sum_{i\in&amp;space;A,j\in&amp;space;\bar{A}}w_{ij}\left&amp;space;(&amp;space;\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}+2+\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}&amp;space;\right&amp;space;)+\frac{1}{2}\sum_{i\in&amp;space;\bar{A},j\in&amp;space;A}w_{ij}\left&amp;space;(&amp;space;\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}+2+\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;\left&amp;space;(&amp;space;\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}+2+\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}&amp;space;\right&amp;space;)\cdot&amp;space;\frac{1}{2}\cdot&amp;space;\left&amp;space;[&amp;space;\sum_{i\in&amp;space;A,j\in&amp;space;\bar{A}}w_{ij}+\sum_{i\in&amp;space;\bar{A},j\in&amp;space;A}w_{ij}&amp;space;\right&amp;space;]"/>
       </div>
       <div>
        而
        <img src="http://latex.codecogs.com/gif.latex?\frac{1}{2}\cdot&amp;space;\left&amp;space;[&amp;space;\sum_{i\in&amp;space;A,j\in&amp;space;\bar{A}}w_{ij}+\sum_{i\in&amp;space;\bar{A},j\in&amp;space;A}w_{ij}&amp;space;\right&amp;space;]=\frac{1}{2}\sum_{i=1}^{k}W\left&amp;space;(&amp;space;A_i,\bar{A}_i&amp;space;\right&amp;space;)=cut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;cut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)\left&amp;space;(&amp;space;\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|+\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}+\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|+\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;\left&amp;space;(&amp;space;\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|+\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|&amp;space;\right&amp;space;)\left&amp;space;(&amp;space;\frac{cut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}+\frac{cut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        而
        <img src="http://latex.codecogs.com/gif.latex?\left&amp;space;(&amp;space;\frac{cut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}+\frac{cut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}&amp;space;\right&amp;space;)=\sum_{i=1}^{k}\frac{cut\left&amp;space;(&amp;space;A_i,\bar{A}_i&amp;space;\right&amp;space;)}{\left&amp;space;|&amp;space;A_i&amp;space;\right&amp;space;|}=RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;\left&amp;space;(&amp;space;\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|+\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|&amp;space;\right&amp;space;)\cdot&amp;space;RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;\left&amp;space;|&amp;space;V&amp;space;\right&amp;space;|\cdot&amp;space;RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        其中，
        <img src="http://latex.codecogs.com/gif.latex?\left&amp;space;|&amp;space;V&amp;space;\right&amp;space;|"/>
        表示的是顶点的数目，对于确定的图来说是个常数。由上述的推导可知，由
        <img src="http://latex.codecogs.com/gif.latex?{f}'Lf"/>
        推导出了
        <img src="http://latex.codecogs.com/gif.latex?RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
        ，由此可知：Laplacian矩阵与有优化的目标函数
        <img src="http://latex.codecogs.com/gif.latex?RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
        之间存在密切的联系。
       </div>
       <h2>
        <p name="t16">
        </p>
        2、新的目标函数
       </h2>
       <div>
        由上式可得：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?{f}'Lf=\left&amp;space;|&amp;space;V&amp;space;\right&amp;space;|\cdot&amp;space;RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
       </div>
       <div>
        由于
        <img src="http://latex.codecogs.com/gif.latex?\left&amp;space;|&amp;space;V&amp;space;\right&amp;space;|"/>
        是个常数，故要求
        <img src="http://latex.codecogs.com/gif.latex?RatioCut\left&amp;space;(&amp;space;A,\bar{A}&amp;space;\right&amp;space;)"/>
        的最小值，即求
        <img src="http://latex.codecogs.com/gif.latex?{f}'Lf"/>
        的最小值。则新的目标函数为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\underset{f\in&amp;space;R^n}{min}\;&amp;space;{f}'Lf"/>
        <img src="http://latex.codecogs.com/gif.latex?s.t.f\perp&amp;space;I,\left&amp;space;\|&amp;space;f&amp;space;\right&amp;space;\|=\sqrt{n}"/>
       </div>
       <div>
        其中
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?f_i=\begin{cases}&amp;space;\sqrt{\frac{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}}&amp;space;&amp;&amp;space;\text{&amp;space;if&amp;space;}&amp;space;v_i\in&amp;space;A&amp;space;\\&amp;space;-\sqrt{\frac{\left&amp;space;|&amp;space;A&amp;space;\right&amp;space;|}{\left&amp;space;|&amp;space;\bar{A}&amp;space;\right&amp;space;|}}&amp;space;&amp;&amp;space;\text{&amp;space;if&amp;space;}&amp;space;v_i\in&amp;space;\bar{A}&amp;space;\end{cases}"/>
       </div>
       <h2>
        <p name="t17">
        </p>
        3、转化到Laplacian矩阵的求解
       </h2>
       <div>
        假设
        <img src="http://latex.codecogs.com/gif.latex?\lambda"/>
        是Laplacian矩阵
        <img src="http://latex.codecogs.com/gif.latex?L"/>
        的特征值，
        <img src="http://latex.codecogs.com/gif.latex?f"/>
        是特征值
        <img src="http://latex.codecogs.com/gif.latex?\lambda"/>
        对应的特征向量，则有：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?Lf=\lambda&amp;space;f"/>
       </div>
       <div>
        在上式的两端同时左乘
        <img src="http://latex.codecogs.com/gif.latex?{f}'"/>
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\Rightarrow&amp;space;{f}'Lf=\lambda&amp;space;{f}'f"/>
       </div>
       <div>
        已知
        <img src="http://latex.codecogs.com/gif.latex?\left&amp;space;\|&amp;space;f&amp;space;\right&amp;space;\|=\sqrt{n}"/>
        ，则
        <img src="http://latex.codecogs.com/gif.latex?{f}'f=n"/>
        ，上式可以转化为：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?{f}'Lf=\lambda&amp;space;n"/>
       </div>
       <div>
        要求
        <img src="http://latex.codecogs.com/gif.latex?\underset{f\in&amp;space;R^n}{min}\;&amp;space;{f}'Lf"/>
        ，即只需求得最小特征值
        <img src="http://latex.codecogs.com/gif.latex?\lambda"/>
        。由Laplacian矩阵的性质可知，Laplacian矩阵的最小特征值为
        <img src="http://latex.codecogs.com/gif.latex?0"/>
        。由Rayleigh-Ritz理论，可以取第2小特征值。
       </div>
       <div>
        <img src="http://img.blog.csdn.net/20150515111812387?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZ2xlMTk4OTAxMDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast"/>
       </div>
       <h1>
        <p name="t18">
        </p>
        五、从二类别聚类到多类别聚类
       </h1>
       <h2>
        <p name="t19">
        </p>
        1、二类别聚类
       </h2>
       <div>
        对于求解出来的特征向量
        <img src="http://latex.codecogs.com/gif.latex?f={\left&amp;space;(&amp;space;f_1,\cdots&amp;space;,f_n&amp;space;\right&amp;space;)}'\in&amp;space;R^n"/>
        中的每一个分量
        <img src="http://latex.codecogs.com/gif.latex?f_i"/>
        ，根据每个分量的值来判断对应的点所属的类别：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\left\{\begin{matrix}&amp;space;v_i\in&amp;space;A&amp;&amp;space;if\;&amp;space;f_i\geq&amp;space;0\\&amp;space;v_i\in&amp;space;\bar{A}&amp;&amp;space;if\;&amp;space;f_i%3C0&amp;space;\end{matrix}\right."/>
       </div>
       <h2>
        <p name="t20">
        </p>
        2、多类别聚类
       </h2>
       <div>
        对于求出来的前
        <em>
         k
        </em>
        个特征向量，可以利用K-Means聚类方法对其进行聚类，若前
        <img src="http://latex.codecogs.com/gif.latex?k"/>
        个特征向量为
        <img src="http://latex.codecogs.com/gif.latex?f^{(1)},f^{(2)},\cdots&amp;space;,f^{(k)}"/>
        ，这样便由特征向量构成如下的特征向量矩阵：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?\begin{pmatrix}&amp;space;f^{(1)}_1&amp;space;&amp;&amp;space;f^{(2)}_1&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;f^{(k)}_1\\&amp;space;f^{(1)}_2&amp;space;&amp;&amp;space;f^{(2)}_2&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;f^{(k)}_2\\&amp;space;\vdots&amp;space;&amp;&amp;space;\vdots&amp;space;&amp;&amp;space;&amp;&amp;space;\vdots&amp;space;\\&amp;space;f^{(1)}_n&amp;space;&amp;&amp;space;f^{(2)}_n&amp;space;&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;f^{(k)}_n&amp;space;\end{pmatrix}_{n\times&amp;space;k}"/>
       </div>
       <div>
        将特征向量矩阵中的每一行最为一个样本，利用K-Means聚类方法对其进行聚类。
       </div>
       <h1>
        <p name="t21">
        </p>
        六、谱聚类的过程
       </h1>
       <h2>
        <p name="t22">
        </p>
        1、基本的结构
       </h2>
       <div>
        基于以上的分析，谱聚类的基本过程为：
       </div>
       <div>
        <ol>
         <li>
          对于给定的图
          <em>
           G=(V,E)
          </em>
          ，求图的度矩阵
          <em>
           D
          </em>
          和邻接矩阵
          <em>
           A
          </em>
          ；
         </li>
         <li>
          计算图的Laplacian矩阵
          <em>
           L=D-A
          </em>
          ；
         </li>
         <li>
          对Laplacian矩阵进行特征值分解，取其前
          <img src="http://latex.codecogs.com/gif.latex?k"/>
          个特征值对应的特征向量，构成n*k的特征向量矩阵；
         </li>
         <li>
          利用K-Means聚类算法对上述的
          <img src="http://latex.codecogs.com/gif.latex?n\times&amp;space;k"/>
          的特征向量矩阵进行聚类，每一行代表一个样本点。
         </li>
        </ol>
        <h2>
         <p name="t23">
         </p>
         2、利用相似度矩阵的构造方法
        </h2>
       </div>
       <div>
        上述的方法是通过图的度矩阵
        <img src="http://latex.codecogs.com/gif.latex?D"/>
        和邻接矩阵
        <img src="http://latex.codecogs.com/gif.latex?A"/>
        来构造Laplacian矩阵，也可以通过相似度矩阵的方法构造Laplacian矩阵，其方法如下：
       </div>
       <div>
        相似度矩阵是由权值矩阵得到：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?S=\begin{pmatrix}&amp;space;s_{11}&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;s_{1n}\\&amp;space;\vdots&amp;space;&amp;&amp;space;&amp;&amp;space;\vdots&amp;space;\\&amp;space;s_{n1}&amp;&amp;space;\cdots&amp;space;&amp;&amp;space;s_{nn}&amp;space;\end{pmatrix}"/>
       </div>
       <div>
        其中
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?s_{ij}=e^{-\frac{\left&amp;space;(&amp;space;w_{ij}&amp;space;\right&amp;space;)^2}{2\sigma&amp;space;^2}}"/>
       </div>
       <div>
        再利用相似度矩阵
        <em>
         S
        </em>
        构造Laplacian矩阵：
       </div>
       <div>
        <img src="http://latex.codecogs.com/gif.latex?L=D^{-\frac{1}{2}}SD^{-\frac{1}{2}}"/>
       </div>
       <div>
        其中
        <em>
         D
        </em>
        为相似度矩阵
        <em>
         S
        </em>
        的度矩阵。
       </div>
       <div>
        注意：在第一种方法中，求解的是Laplacian矩阵的前
        <em>
         k
        </em>
        个最小特征值对应的特征向量，在第二种方法中，求解的是Laplacian矩阵的前
        <img src="http://latex.codecogs.com/gif.latex?k"/>
        个最大特征值对应的特征向量
       </div>
       <h1>
        <p name="t24">
        </p>
        七、实验代码
       </h1>
       <h2>
        <p name="t25">
        </p>
        1、自己实现的一个
       </h2>
       <div>
        <div class="dp-highlighter bg_python">
         <div class="bar">
          <div class="tools">
           <b>
            [python]
           </b>
           <a class="ViewSource" href="http://blog.csdn.net/google19890102/article/details/45697695" title="view plain">
            view plain
           </a>
           <a class="CopyToClipboard" href="http://blog.csdn.net/google19890102/article/details/45697695" title="copy">
            copy
           </a>
          </div>
         </div>
         <ol class="dp-py" start="1">
          <li class="alt">
           <span class="comment">
            #coding:UTF-8
           </span>
          </li>
          <li class="">
           <span class="string">
            ”
           </span>
           <span class="comment">
            ”’
           </span>
          </li>
          <li class="alt">
           <span class="comment">
            Created on 2015年5月12日
           </span>
          </li>
          <li class="">
          </li>
          <li class="alt">
           <span class="comment">
            @author: zhaozhiyong
           </span>
          </li>
          <li class="">
           <span class="comment">
            ”’
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            from
           </span>
           __future__
           <span class="keyword">
            import
           </span>
           division
          </li>
          <li class="">
           <span class="keyword">
            import
           </span>
           scipy.io as scio
          </li>
          <li class="alt">
           <span class="keyword">
            from
           </span>
           scipy
           <span class="keyword">
            import
           </span>
           sparse
          </li>
          <li class="">
           <span class="keyword">
            from
           </span>
           scipy.sparse.linalg.eigen
           <span class="keyword">
            import
           </span>
           arpack
           <span class="comment">
            #这里只能这么做，不然始终找不到函数eigs
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            from
           </span>
           numpy
           <span class="keyword">
            import
           </span>
           *
          </li>
          <li class="">
          </li>
          <li class="alt">
          </li>
          <li class="">
           <span class="keyword">
            def
           </span>
           spectalCluster(data, sigma, num_clusters):
          </li>
          <li class="alt">
           <span class="keyword">
            print
           </span>
           <span class="string">
            “将邻接矩阵转换成相似矩阵”
           </span>
          </li>
          <li class="">
           <span class="comment">
            #先完成sigma ！= 0
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            print
           </span>
           <span class="string">
            “Fixed-sigma谱聚类”
           </span>
          </li>
          <li class="">
           data = sparse.csc_matrix.multiply(data, data)
          </li>
          <li class="alt">
          </li>
          <li class="">
           data = -data / (
           <span class="number">
            2
           </span>
           * sigma * sigma)
          </li>
          <li class="alt">
          </li>
          <li class="">
           S = sparse.csc_matrix.expm1(data) + sparse.csc_matrix.multiply(sparse.csc_matrix.sign(data), sparse.csc_matrix.sign(data))
          </li>
          <li class="alt">
          </li>
          <li class="">
           <span class="comment">
            #转换成Laplacian矩阵
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            print
           </span>
           <span class="string">
            “将相似矩阵转换成Laplacian矩阵”
           </span>
          </li>
          <li class="">
           D = S.sum(
           <span class="number">
            1
           </span>
           )
           <span class="comment">
            #相似矩阵是对称矩阵
           </span>
          </li>
          <li class="alt">
           D = sqrt(
           <span class="number">
            1
           </span>
           / D)
          </li>
          <li class="">
           n = len(D)
          </li>
          <li class="alt">
           D = D.T
          </li>
          <li class="">
           D = sparse.spdiags(D,
           <span class="number">
            0
           </span>
           , n, n)
          </li>
          <li class="alt">
           L = D * S * D
          </li>
          <li class="">
          </li>
          <li class="alt">
           <span class="comment">
            #求特征值和特征向量
           </span>
          </li>
          <li class="">
           <span class="keyword">
            print
           </span>
           <span class="string">
            “求特征值和特征向量”
           </span>
          </li>
          <li class="alt">
           vals, vecs = arpack.eigs(L, k=num_clusters,tol=
           <span class="number">
            0
           </span>
           ,which=
           <span class="string">
            “LM”
           </span>
           )
          </li>
          <li class="">
          </li>
          <li class="alt">
           <span class="comment">
            # 利用k-Means
           </span>
          </li>
          <li class="">
           <span class="keyword">
            print
           </span>
           <span class="string">
            “利用K-Means对特征向量聚类”
           </span>
          </li>
          <li class="alt">
           <span class="comment">
            #对vecs做正规化
           </span>
          </li>
          <li class="">
           sq_sum = sqrt(multiply(vecs,vecs).sum(
           <span class="number">
            1
           </span>
           ))
          </li>
          <li class="alt">
           m_1, m_2 = shape(vecs)
          </li>
          <li class="">
           <span class="keyword">
            for
           </span>
           i
           <span class="keyword">
            in
           </span>
           xrange(m_1):
          </li>
          <li class="alt">
           <span class="keyword">
            for
           </span>
           j
           <span class="keyword">
            in
           </span>
           xrange(m_2):
          </li>
          <li class="">
           vecs[i,j] = vecs[i,j]/sq_sum[i]
          </li>
          <li class="alt">
          </li>
          <li class="">
           myCentroids, clustAssing = kMeans(vecs, num_clusters)
          </li>
          <li class="alt">
          </li>
          <li class="">
           <span class="keyword">
            for
           </span>
           i
           <span class="keyword">
            in
           </span>
           xrange(shape(clustAssing)[
           <span class="number">
            0
           </span>
           ]):
          </li>
          <li class="alt">
           <span class="keyword">
            print
           </span>
           clustAssing[i,
           <span class="number">
            0
           </span>
           ]
          </li>
          <li class="">
          </li>
          <li class="alt">
          </li>
          <li class="">
           <span class="keyword">
            def
           </span>
           randCent(dataSet, k):
          </li>
          <li class="alt">
           n = shape(dataSet)[
           <span class="number">
            1
           </span>
           ]
          </li>
          <li class="">
           centroids = mat(zeros((k,n)))
           <span class="comment">
            #create centroid mat
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            for
           </span>
           j
           <span class="keyword">
            in
           </span>
           range(n):
           <span class="comment">
            #create random cluster centers, within bounds of each dimension
           </span>
          </li>
          <li class="">
           minJ = min(dataSet[:,j])
          </li>
          <li class="alt">
           rangeJ = float(max(dataSet[:,j]) – minJ)
          </li>
          <li class="">
           centroids[:,j] = mat(minJ + rangeJ * random.rand(k,
           <span class="number">
            1
           </span>
           ))
          </li>
          <li class="alt">
           <span class="keyword">
            return
           </span>
           centroids
          </li>
          <li class="">
          </li>
          <li class="alt">
           <span class="keyword">
            def
           </span>
           distEclud(vecA, vecB):
          </li>
          <li class="">
           <span class="keyword">
            return
           </span>
           sqrt(sum(power(vecA – vecB,
           <span class="number">
            2
           </span>
           )))
           <span class="comment">
            #la.norm(vecA-vecB)
           </span>
          </li>
          <li class="alt">
          </li>
          <li class="">
           <span class="keyword">
            def
           </span>
           kMeans(dataSet, k):
          </li>
          <li class="alt">
           m = shape(dataSet)[
           <span class="number">
            0
           </span>
           ]
          </li>
          <li class="">
           clusterAssment = mat(zeros((m,
           <span class="number">
            2
           </span>
           )))
           <span class="comment">
            #create mat to assign data points to a centroid, also holds SE of each point
           </span>
          </li>
          <li class="alt">
           centroids = randCent(dataSet, k)
          </li>
          <li class="">
           clusterChanged =
           <span class="special">
            True
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            while
           </span>
           clusterChanged:
          </li>
          <li class="">
           clusterChanged =
           <span class="special">
            False
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            for
           </span>
           i
           <span class="keyword">
            in
           </span>
           range(m):
           <span class="comment">
            #for each data point assign it to the closest centroid
           </span>
          </li>
          <li class="">
           minDist = inf; minIndex = –
           <span class="number">
            1
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            for
           </span>
           j
           <span class="keyword">
            in
           </span>
           range(k):
          </li>
          <li class="">
           distJI = distEclud(centroids[j,:],dataSet[i,:])
          </li>
          <li class="alt">
           <span class="keyword">
            if
           </span>
           distJI &lt; minDist:
          </li>
          <li class="">
           minDist = distJI; minIndex = j
          </li>
          <li class="alt">
           <span class="keyword">
            if
           </span>
           clusterAssment[i,
           <span class="number">
            0
           </span>
           ] != minIndex: clusterChanged =
           <span class="special">
            True
           </span>
          </li>
          <li class="">
           clusterAssment[i,:] = minIndex,minDist**
           <span class="number">
            2
           </span>
          </li>
          <li class="alt">
           <span class="comment">
            #print centroids
           </span>
          </li>
          <li class="">
           <span class="keyword">
            for
           </span>
           cent
           <span class="keyword">
            in
           </span>
           range(k):
           <span class="comment">
            #recalculate centroids
           </span>
          </li>
          <li class="alt">
           ptsInClust = dataSet[nonzero(clusterAssment[:,
           <span class="number">
            0
           </span>
           ].A==cent)[
           <span class="number">
            0
           </span>
           ]]
           <span class="comment">
            #get all the point in this cluster
           </span>
          </li>
          <li class="">
           centroids[cent,:] = mean(ptsInClust, axis=
           <span class="number">
            0
           </span>
           )
           <span class="comment">
            #assign centroid to mean
           </span>
          </li>
          <li class="alt">
           <span class="keyword">
            return
           </span>
           centroids, clusterAssment
          </li>
          <li class="">
          </li>
          <li class="alt">
          </li>
          <li class="">
           <span class="keyword">
            if
           </span>
           __name__ ==
           <span class="string">
            ‘__main__’
           </span>
           :
          </li>
          <li class="alt">
           <span class="comment">
            # 导入数据集
           </span>
          </li>
          <li class="">
           matf =
           <span class="string">
            ‘E://data_sc//corel_50_NN_sym_distance.mat’
           </span>
          </li>
          <li class="alt">
           dataDic = scio.loadmat(matf)
          </li>
          <li class="">
           data = dataDic[
           <span class="string">
            ‘A’
           </span>
           ]
          </li>
          <li class="alt">
           <span class="comment">
            # 谱聚类的过程
           </span>
          </li>
          <li class="">
           spectalCluster(data,
           <span class="number">
            20
           </span>
           ,
           <span class="number">
            18
           </span>
           )
          </li>
         </ol>
        </div>
        <h2>
         <p name="t26">
         </p>
         2、网上提供的一个Matlab代码
        </h2>
       </div>
       <div>
        <div class="dp-highlighter bg_plain">
         <div class="bar">
          <div class="tools">
           <b>
            [plain]
           </b>
           <a class="ViewSource" href="http://blog.csdn.net/google19890102/article/details/45697695" title="view plain">
            view plain
           </a>
           <a class="CopyToClipboard" href="http://blog.csdn.net/google19890102/article/details/45697695" title="copy">
            copy
           </a>
          </div>
         </div>
         <ol start="1">
          <li class="alt">
           function [cluster_labels evd_time kmeans_time total_time] = sc(A, sigma, num_clusters)
          </li>
          <li class="">
           %SC Spectral clustering using a sparse similarity matrix (t-nearest-neighbor).
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           %   Input  : A              : N-by-N sparse distance matrix, where
          </li>
          <li class="alt">
           %                             N is the number of data
          </li>
          <li class="">
           %            sigma          : sigma value used in computing similarity,
          </li>
          <li class="alt">
           %                             if 0, apply self-tunning technique
          </li>
          <li class="">
           %            num_clusters   : number of clusters
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           %   Output : cluster_labels : N-by-1 vector containing cluster labels
          </li>
          <li class="alt">
           %            evd_time       : running time for eigendecomposition
          </li>
          <li class="">
           %            kmeans_time    : running time for k-means
          </li>
          <li class="alt">
           %            total_time     : total running time
          </li>
          <li class="">
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           % Convert the sparse distance matrix to a sparse similarity matrix,
          </li>
          <li class="alt">
           % where S = exp^(-(A^2 / 2*sigma^2)).
          </li>
          <li class="">
           % Note: This step can be ignored if A is sparse similarity matrix.
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           disp(‘Converting distance matrix to similarity matrix…’);
          </li>
          <li class="alt">
           tic;
          </li>
          <li class="">
           n = size(A, 1);
          </li>
          <li class="alt">
          </li>
          <li class="">
           if (sigma == 0) % Selftuning spectral clustering
          </li>
          <li class="alt">
           % Find the count of nonzero for each column
          </li>
          <li class="">
           disp(‘Selftuning spectral clustering…’);
          </li>
          <li class="alt">
           col_count = sum(A~=0, 1)’;
          </li>
          <li class="">
           col_sum = sum(A, 1)’;
          </li>
          <li class="alt">
           col_mean = col_sum ./ col_count;
          </li>
          <li class="">
           [x y val] = find(A);
          </li>
          <li class="alt">
           A = sparse(x, y, -val.*val./col_mean(x)./col_mean(y)./2);
          </li>
          <li class="">
           clear col_count col_sum col_mean x y val;
          </li>
          <li class="alt">
           else % Fixed-sigma spectral clustering
          </li>
          <li class="">
           disp(‘Fixed-sigma spectral clustering…’);
          </li>
          <li class="alt">
           A = A.*A;
          </li>
          <li class="">
           A = -A/(2*sigma*sigma);
          </li>
          <li class="alt">
           end
          </li>
          <li class="">
          </li>
          <li class="alt">
           % Do exp function sequentially because of memory limitation
          </li>
          <li class="">
           num = 2000;
          </li>
          <li class="alt">
           num_iter = ceil(n/num);
          </li>
          <li class="">
           S = sparse([]);
          </li>
          <li class="alt">
           for i = 1:num_iter
          </li>
          <li class="">
           start_index = 1 + (i-1)*num;
          </li>
          <li class="alt">
           end_index = min(i*num, n);
          </li>
          <li class="">
           S1 = spfun(@exp, A(:,start_index:end_index)); % sparse exponential func
          </li>
          <li class="alt">
           S = [S S1];
          </li>
          <li class="">
           clear S1;
          </li>
          <li class="alt">
           end
          </li>
          <li class="">
           clear A;
          </li>
          <li class="alt">
           toc;
          </li>
          <li class="">
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           % Do laplacian, L = D^(-1/2) * S * D^(-1/2)
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           disp(‘Doing Laplacian…’);
          </li>
          <li class="alt">
           D = sum(S, 2) + (1e-10);
          </li>
          <li class="">
           D = sqrt(1./D); % D^(-1/2)
          </li>
          <li class="alt">
           D = spdiags(D, 0, n, n);
          </li>
          <li class="">
           L = D * S * D;
          </li>
          <li class="alt">
           clear D S;
          </li>
          <li class="">
           time1 = toc;
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Do eigendecomposition, if L =
          </li>
          <li class="">
           %   D^(-1/2) * S * D(-1/2)    : set ‘LM’ (Largest Magnitude), or
          </li>
          <li class="alt">
           %   I – D^(-1/2) * S * D(-1/2): set ‘SM’ (Smallest Magnitude).
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           disp(‘Performing eigendecomposition…’);
          </li>
          <li class="">
           OPTS.disp = 0;
          </li>
          <li class="alt">
           [V, val] = eigs(L, num_clusters, ‘LM’, OPTS);
          </li>
          <li class="">
           time2 = toc;
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Do k-means
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           disp(‘Performing kmeans…’);
          </li>
          <li class="">
           % Normalize each row to be of unit length
          </li>
          <li class="alt">
           sq_sum = sqrt(sum(V.*V, 2)) + 1e-20;
          </li>
          <li class="">
           U = V ./ repmat(sq_sum, 1, num_clusters);
          </li>
          <li class="alt">
           clear sq_sum V;
          </li>
          <li class="">
           cluster_labels = k_means(U, [], num_clusters);
          </li>
          <li class="alt">
           total_time = toc;
          </li>
          <li class="">
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           % Calculate and show time statistics
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           evd_time = time2 – time1
          </li>
          <li class="alt">
           kmeans_time = total_time – time2
          </li>
          <li class="">
           total_time
          </li>
          <li class="alt">
           disp(‘Finished!’);
          </li>
         </ol>
        </div>
        <div class="dp-highlighter bg_plain">
         <div class="bar">
          <div class="tools">
           <b>
            [plain]
           </b>
           <a class="ViewSource" href="http://blog.csdn.net/google19890102/article/details/45697695" title="view plain">
            view plain
           </a>
           <a class="CopyToClipboard" href="http://blog.csdn.net/google19890102/article/details/45697695" title="copy">
            copy
           </a>
          </div>
         </div>
         <ol start="1">
          <li class="alt">
           function cluster_labels = k_means(data, centers, num_clusters)
          </li>
          <li class="">
           %K_MEANS Euclidean k-means clustering algorithm.
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           %   Input    : data           : N-by-D data matrix, where N is the number of data,
          </li>
          <li class="alt">
           %                               D is the number of dimensions
          </li>
          <li class="">
           %              centers        : K-by-D matrix, where K is num_clusters, or
          </li>
          <li class="alt">
           %                               ‘random’, random initialization, or
          </li>
          <li class="">
           %                               [], empty matrix, orthogonal initialization
          </li>
          <li class="alt">
           %              num_clusters   : Number of clusters
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           %   Output   : cluster_labels : N-by-1 vector of cluster assignment
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           %   Reference: Dimitrios Zeimpekis, Efstratios Gallopoulos, 2006.
          </li>
          <li class="">
           %              http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Parameter setting
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           iter = 0;
          </li>
          <li class="">
           qold = inf;
          </li>
          <li class="alt">
           threshold = 0.001;
          </li>
          <li class="">
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           % Check if with initial centers
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           if strcmp(centers, ‘random’)
          </li>
          <li class="alt">
           disp(‘Random initialization…’);
          </li>
          <li class="">
           centers = random_init(data, num_clusters);
          </li>
          <li class="alt">
           elseif isempty(centers)
          </li>
          <li class="">
           disp(‘Orthogonal initialization…’);
          </li>
          <li class="alt">
           centers = orth_init(data, num_clusters);
          </li>
          <li class="">
           end
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Double type is required for sparse matrix multiply
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           data = double(data);
          </li>
          <li class="">
           centers = double(centers);
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Calculate the distance (square) between data and centers
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           n = size(data, 1);
          </li>
          <li class="">
           x = sum(data.*data, 2)’;
          </li>
          <li class="alt">
           X = x(ones(num_clusters, 1), :);
          </li>
          <li class="">
           y = sum(centers.*centers, 2);
          </li>
          <li class="alt">
           Y = y(:, ones(n, 1));
          </li>
          <li class="">
           P = X + Y – 2*centers*data’;
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Main program
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           while 1
          </li>
          <li class="">
           iter = iter + 1;
          </li>
          <li class="alt">
          </li>
          <li class="">
           % Find the closest cluster for each data point
          </li>
          <li class="alt">
           [val, ind] = min(P, [], 1);
          </li>
          <li class="">
           % Sum up data points within each cluster
          </li>
          <li class="alt">
           P = sparse(ind, 1:n, 1, num_clusters, n);
          </li>
          <li class="">
           centers = P*data;
          </li>
          <li class="alt">
           % Size of each cluster, for cluster whose size is 0 we keep it empty
          </li>
          <li class="">
           cluster_size = P*ones(n, 1);
          </li>
          <li class="alt">
           % For empty clusters, initialize again
          </li>
          <li class="">
           zero_cluster = find(cluster_size==0);
          </li>
          <li class="alt">
           if length(zero_cluster) &gt; 0
          </li>
          <li class="">
           disp(‘Zero centroid. Initialize again…’);
          </li>
          <li class="alt">
           centers(zero_cluster, :)= random_init(data, length(zero_cluster));
          </li>
          <li class="">
           cluster_size(zero_cluster) = 1;
          </li>
          <li class="alt">
           end
          </li>
          <li class="">
           % Update centers
          </li>
          <li class="alt">
           centers = spdiags(1./cluster_size, 0, num_clusters, num_clusters)*centers;
          </li>
          <li class="">
          </li>
          <li class="alt">
           % Update distance (square) to new centers
          </li>
          <li class="">
           y = sum(centers.*centers, 2);
          </li>
          <li class="alt">
           Y = y(:, ones(n, 1));
          </li>
          <li class="">
           P = X + Y – 2*centers*data’;
          </li>
          <li class="alt">
          </li>
          <li class="">
           % Calculate objective function value
          </li>
          <li class="alt">
           qnew = sum(sum(sparse(ind, 1:n, 1, size(P, 1), size(P, 2)).*P));
          </li>
          <li class="">
           mesg = sprintf(‘Iteration %d:\n\tQold=%g\t\tQnew=%g’, iter, full(qold), full(qnew));
          </li>
          <li class="alt">
           disp(mesg);
          </li>
          <li class="">
          </li>
          <li class="alt">
           % Check if objective function value is less than/equal to threshold
          </li>
          <li class="">
           if threshold &gt;= abs((qnew-qold)/qold)
          </li>
          <li class="alt">
           mesg = sprintf(‘\nkmeans converged!’);
          </li>
          <li class="">
           disp(mesg);
          </li>
          <li class="alt">
           break;
          </li>
          <li class="">
           end
          </li>
          <li class="alt">
           qold = qnew;
          </li>
          <li class="">
           end
          </li>
          <li class="alt">
          </li>
          <li class="">
           cluster_labels = ind’;
          </li>
          <li class="alt">
          </li>
          <li class="">
          </li>
          <li class="alt">
           %—————————————————————————–
          </li>
          <li class="">
           function init_centers = random_init(data, num_clusters)
          </li>
          <li class="alt">
           %RANDOM_INIT Initialize centroids choosing num_clusters rows of data at random
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           %   Input : data         : N-by-D data matrix, where N is the number of data,
          </li>
          <li class="">
           %                          D is the number of dimensions
          </li>
          <li class="alt">
           %           num_clusters : Number of clusters
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           %   Output: init_centers : K-by-D matrix, where K is num_clusters
          </li>
          <li class="">
           rand(‘twister’, sum(100*clock));
          </li>
          <li class="alt">
           init_centers = data(ceil(size(data, 1)*rand(1, num_clusters)), :);
          </li>
          <li class="">
          </li>
          <li class="alt">
           function init_centers = orth_init(data, num_clusters)
          </li>
          <li class="">
           %ORTH_INIT Initialize orthogonal centers for k-means clustering algorithm.
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           %   Input : data         : N-by-D data matrix, where N is the number of data,
          </li>
          <li class="alt">
           %                          D is the number of dimensions
          </li>
          <li class="">
           %           num_clusters : Number of clusters
          </li>
          <li class="alt">
           %
          </li>
          <li class="">
           %   Output: init_centers : K-by-D matrix, where K is num_clusters
          </li>
          <li class="alt">
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           % Find the num_clusters centers which are orthogonal to each other
          </li>
          <li class="">
           %
          </li>
          <li class="alt">
           Uniq = unique(data, ‘rows’); % Avoid duplicate centers
          </li>
          <li class="">
           num = size(Uniq, 1);
          </li>
          <li class="alt">
           first = ceil(rand(1)*num); % Randomly select the first center
          </li>
          <li class="">
           init_centers = zeros(num_clusters, size(data, 2)); % Storage for centers
          </li>
          <li class="alt">
           init_centers(1,
           <img src="http://dataunion.org/wp-includes/images/smilies/simple-smile.png"/>
           = Uniq(first, :);
          </li>
          <li class="">
           Uniq(first,
           <img src="http://dataunion.org/wp-includes/images/smilies/simple-smile.png"/>
           = [];
          </li>
          <li class="alt">
           c = zeros(num-1, 1); % Accumalated orthogonal values to existing centers for non-centers
          </li>
          <li class="">
           % Find the rest num_clusters-1 centers
          </li>
          <li class="alt">
           for j = 2:num_clusters
          </li>
          <li class="">
           c = c + abs(Uniq*init_centers(j-1, :)’);
          </li>
          <li class="alt">
           [minimum, i] = min(c); % Select the most orthogonal one as next center
          </li>
          <li class="">
           init_centers(j,
           <img src="http://dataunion.org/wp-includes/images/smilies/simple-smile.png"/>
           = Uniq(i, :);
          </li>
          <li class="alt">
           Uniq(i,
           <img src="http://dataunion.org/wp-includes/images/smilies/simple-smile.png"/>
           = [];
          </li>
          <li class="">
           c(i) = [];
          </li>
          <li class="alt">
           end
          </li>
          <li class="">
           clear c Uniq;
          </li>
         </ol>
        </div>
        <p>
         个人的一点认识：谱聚类的过程相当于先进行一个非线性的降维，然后在这样的低维空间中再利用聚类的方法进行聚类。
        </p>
       </div>
       <div>
        欢迎大家一起讨论，如有问题欢迎留言，欢迎大家转载。
       </div>
       <p>
        参考
       </p>
       <p>
        1、从拉普拉斯矩阵说到谱聚类(http://blog.csdn.net/v_july_v/article/details/40738211)
       </p>
       <p>
        2、
        <a class="postTitle2" href="http://www.cnblogs.com/FengYan/archive/2012/06/21/2553999.html" id="cb_post_title_url" target="_blank">
         谱聚类
        </a>
        <a class="postTitle2" href="http://www.cnblogs.com/FengYan/archive/2012/06/21/2553999.html" target="_blank">
         (spectral clustering)
        </a>
        (http://www.cnblogs.com/FengYan/archive/2012/06/21/2553999.html)
       </p>
       <p>
        3、
        <a class="postTitle2" href="http://www.cnblogs.com/sparkwen/p/3155850.html" id="cb_post_title_url" target="_blank">
         谱聚类算法
        </a>
        <a class="postTitle2" href="http://www.cnblogs.com/sparkwen/p/3155850.html" target="_blank">
         (Spectral Clustering)
        </a>
        (http://www.cnblogs.com/sparkwen/p/3155850.html)
       </p>
      </div>
      <div>
       <strong>
        注：转载文章均来自于公开网络，仅供学习使用，不会用于任何商业用途，如果侵犯到原作者的权益，请您与我们联系删除或者授权事宜，联系邮箱：contact@dataunion.org。转载数盟网站文章请注明原文章作者，否则产生的任何版权纠纷与数盟无关。
       </strong>
      </div>
      <!--content_text-->
      <div class="fenxian">
       <!-- JiaThis Button BEGIN -->
       <div class="jiathis_style_32x32">
        <p class="jiathis_button_weixin">
        </p>
        <p class="jiathis_button_tsina">
        </p>
        <p class="jiathis_button_qzone">
        </p>
        <p class="jiathis_button_cqq">
        </p>
        <p class="jiathis_button_tumblr">
        </p>
        <a class="jiathis jiathis_txt jtico jtico_jiathis" href="http://www.jiathis.com/share" target="_blank">
        </a>
        <p class="jiathis_counter_style">
        </p>
       </div>
       <!-- JiaThis Button END -->
      </div>
     </article>
     <!--content-->
     <!--相关文章-->
     <div class="xianguan">
      <div class="xianguantitle">
       相关文章！
      </div>
      <ul class="pic">
       <li>
        <a href="http://dataunion.org/20824.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/t018630756a7e263b33-300x165.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20824.html" rel="bookmark" title="如何判断一笔交易是否属于欺诈？你只是需要一点数据挖掘">
         如何判断一笔交易是否属于欺诈？你只是需要一点数据挖掘
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/20820.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/1-300x200.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20820.html" rel="bookmark" title="人们对Python在企业级开发中的10大误解">
         人们对Python在企业级开发中的10大误解
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/20811.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/t0133fcacae8523307b_副本-300x200.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20811.html" rel="bookmark" title="大神亲传：26条深度学习的金科玉律！">
         大神亲传：26条深度学习的金科玉律！
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/20808.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/09/640.webp-11-300x137.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/20808.html" rel="bookmark" title="我们是如何在一张地图上表现86万个数据的">
         我们是如何在一张地图上表现86万个数据的
        </a>
       </li>
      </ul>
     </div>
     <!--相关文章-->
     <div class="comment" id="comments">
      <!-- You can start editing here. -->
      <!-- If comments are open, but there are no comments. -->
      <div class="title">
       期待你一针见血的评论，Come on！
      </div>
      <div id="respond">
       <p>
        不用想啦，马上
        <a href="http://dataunion.org/wp-login.php?redirect_to=http%3A%2F%2Fdataunion.org%2F19721.html">
         "登录"
        </a>
        发表自已的想法.
       </p>
      </div>
     </div>
     <!-- .nav-single -->
    </div>
    <!--Container End-->
    <aside id="sitebar">
     <div class="sitebar_list2">
      <div class="wptag">
       <span class="tagtitle">
        热门标签+
       </span>
       <div class="tagg">
        <ul class="menu" id="menu-%e5%8f%8b%e6%83%85%e9%93%be%e6%8e%a5">
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-1605" id="menu-item-1605">
          <a href="http://taidizh.com/">
           泰迪智慧
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20884" id="menu-item-20884">
          <a href="http://www.transwarp.cn/">
           星环科技
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-3538" id="menu-item-3538">
          <a href="http://datall.org/">
           珈和遥感
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20888" id="menu-item-20888">
          <a href="http://www.chinahadoop.cn/">
           小象学院
          </a>
         </li>
        </ul>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <div class="textwidget">
       <div align="center">
        <a href="http://study.163.com/course/courseMain.htm?courseId=991022" target="_blank">
         <img src="http://dataunion.org/wp-content/uploads/2016/03/dv.jpg"/>
        </a>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       文章分类
      </h4>
      <div class="tagcloud">
       <a class="tag-link-44" href="http://dataunion.org/category/industry/demo" style="font-size: 10.204724409449pt;" title="4个话题">
        Demo展示
       </a>
       <a class="tag-link-31" href="http://dataunion.org/category/experts" style="font-size: 15.826771653543pt;" title="52个话题">
        专家团队
       </a>
       <a class="tag-link-870" href="http://dataunion.org/category/tech/ai" style="font-size: 19.795275590551pt;" title="273个话题">
        人工智能
       </a>
       <a class="tag-link-488" href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f" style="font-size: 8pt;" title="1个话题">
        加入数盟
       </a>
       <a class="tag-link-869" href="http://dataunion.org/category/tech/viz" style="font-size: 17.204724409449pt;" title="93个话题">
        可视化
       </a>
       <a class="tag-link-30" href="http://dataunion.org/category/partners" style="font-size: 10.645669291339pt;" title="5个话题">
        合作伙伴
       </a>
       <a class="tag-link-889" href="http://dataunion.org/category/parterc" style="font-size: 11.582677165354pt;" title="8个话题">
        合作会议
       </a>
       <a class="tag-link-104" href="http://dataunion.org/category/books" style="font-size: 12.96062992126pt;" title="15个话题">
        图书
       </a>
       <a class="tag-link-220" href="http://dataunion.org/category/tech/base" style="font-size: 19.850393700787pt;" title="281个话题">
        基础架构
       </a>
       <a class="tag-link-219" href="http://dataunion.org/category/tech/analysis" style="font-size: 19.409448818898pt;" title="232个话题">
        数据分析
       </a>
       <a class="tag-link-887" href="http://dataunion.org/category/tech/dm" style="font-size: 13.291338582677pt;" title="17个话题">
        数据挖掘
       </a>
       <a class="tag-link-34" href="http://dataunion.org/category/tech" style="font-size: 20.732283464567pt;" title="404个话题">
        文章
       </a>
       <a class="tag-link-1" href="http://dataunion.org/category/uncategorized" style="font-size: 22pt;" title="693个话题">
        未分类
       </a>
       <a class="tag-link-4" href="http://dataunion.org/category/events" style="font-size: 14.503937007874pt;" title="29个话题">
        活动
       </a>
       <a class="tag-link-890" href="http://dataunion.org/category/tech/%e6%b7%b1%e5%ba%a6%e5%ad%a6%e4%b9%a0" style="font-size: 10.204724409449pt;" title="4个话题">
        深度学习
       </a>
       <a class="tag-link-221" href="http://dataunion.org/category/tech/devl" style="font-size: 18.968503937008pt;" title="193个话题">
        编程语言
       </a>
       <a class="tag-link-888" href="http://dataunion.org/category/career" style="font-size: 15.661417322835pt;" title="48个话题">
        职业规划
       </a>
       <a class="tag-link-5" href="http://dataunion.org/category/jobs" style="font-size: 14.11811023622pt;" title="25个话题">
        职位
       </a>
       <a class="tag-link-871" href="http://dataunion.org/category/industry" style="font-size: 15.716535433071pt;" title="49个话题">
        行业
       </a>
       <a class="tag-link-613" href="http://dataunion.org/category/industry/case" style="font-size: 16.984251968504pt;" title="84个话题">
        行业应用
       </a>
       <a class="tag-link-885" href="http://dataunion.org/category/industry/news" style="font-size: 17.425196850394pt;" title="102个话题">
        行业资讯
       </a>
       <a class="tag-link-10" href="http://dataunion.org/category/training" style="font-size: 14.228346456693pt;" title="26个话题">
        课程
       </a>
       <a class="tag-link-16" href="http://dataunion.org/category/sources" style="font-size: 15.661417322835pt;" title="48个话题">
        资源
       </a>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       功能
      </h4>
      <ul>
       <li>
        <a href="http://dataunion.org/wp-login.php?action=register">
         注册
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/wp-login.php">
         登录
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/feed">
         文章
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/comments/feed">
         评论
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="https://cn.wordpress.org/" title="基于WordPress，一个优美、先进的个人信息发布平台。">
         WordPress.org
        </a>
       </li>
      </ul>
     </div>
    </aside>
    <div class="clear">
    </div>
   </div>
   <!--main-->
   ﻿
   <footer id="dibu">
    <div class="about">
     <div class="right">
      <ul class="menu" id="menu-%e5%ba%95%e9%83%a8%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-18024" id="menu-item-18024">
        <a href="http://dataunion.org/category/partners">
         合作伙伴
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20881" id="menu-item-20881">
        <a href="http://dataunion.org/contribute">
         文章投稿
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20872" id="menu-item-20872">
        <a href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f">
         加入数盟
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22441" id="menu-item-22441">
        <a href="http://dataunion.org/f-links">
         友情链接
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20874" id="menu-item-20874">
        <a href="http://dataunion.org/aboutus">
         关于数盟
        </a>
       </li>
      </ul>
      <p class="banquan">
       数盟社区        ，
        做最棒的数据科学社区
      </p>
     </div>
     <div class="left">
      <ul class="bottomlist">
       <li>
        <a href="http://weibo.com/DataScientistUnion  " target="_blank" 　title="">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weibo.png"/>
        </a>
       </li>
       <li>
        <a class="cd-popup-trigger" href="http://dataunion.org/19721.html#0">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weixin.png"/>
        </a>
       </li>
      </ul>
      <div class="cd-popup">
       <div class="cd-popup-container">
        <h1>
         扫描二维码,加微信公众号
        </h1>
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/2014-12-06-1515289049.png"/>
        <a class="cd-popup-close" href="http://dataunion.org/19721.html">
        </a>
       </div>
       <!-- cd-popup-container -->
      </div>
      <!-- cd-popup -->
     </div>
    </div>
    <!--about-->
    <div class="bottom">
     <a href="http://dataunion.org/">
      数盟社区
     </a>
     <a href="http://www.miitbeian.gov.cn/" rel="external nofollow" target="_blank">
      京ICP备14026740号
     </a>
     联系我们：
     <a href="mailto:contact@dataunion.org" target="_blank">
      contact@dataunion.org
     </a>
     <div class="tongji">
     </div>
     <!--bottom-->
     <div class="scroll" id="scroll" style="display:none;">
      ︿
     </div>
    </div>
   </footer>
   <!--dibu-->
  </div>
 </body>
</html>